W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Niniejsze zadanie to trudniejsza wersja zadania Monotoniczność z finału XVII OI. Nie wystąpiła ona w samym konkursie.
Schematem monotoniczności ciągu liczb całkowitych nazwiemy ciąg złożony ze znaków , lub =. Znak reprezentuje relację pomiędzy liczbami i . Na przykład, schematem monotoniczności ciągu jest .
Powiemy, że ciąg liczb , o schemacie monotoniczności , realizuje pewien schemat monotoniczności , jeżeli dla każdego całkowitego zachodzi . Innymi słowy, ciąg uzyskujemy, powtarzając odpowiednio długo ciąg i ewentualnie odrzucając kilka ostatnich wyrazów tego powtórzenia. Na przykład, ciąg realizuje następujące schematy monotoniczności:
Dany jest ciąg liczb całkowitych . Twoim zadaniem jest znalezienie najdłuższego jego podciągu () realizującego pewien zadany schemat monotoniczności .
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające odpowiednio długość ciągu oraz długość schematu monotoniczności .
W drugim wierszu znajduje się liczb całkowitych pooddzielanych pojedynczymi odstępami, oznaczających wyrazy badanego ciągu ().
W trzecim wierszu znajduje się znaków postaci <, > lub =, pooddzielanych pojedynczymi odstępami, oznaczających kolejne wyrazy schematu monotoniczności.
W pierwszym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą oznaczającą maksymalną długość podciągu ciągu realizującego schemat monotoniczności .
W drugim wierszu Twój program powinien wypisać dowolny przykład takiego podciągu , oddzielając jego wyrazy pojedynczymi odstępami.
Dla danych wejściowych:
7 3 2 4 3 1 3 5 3 < > =
poprawną odpowiedzią jest:
6 2 4 3 3 5 3
Autorzy zadania: Marian M. Kędzierski, Piotr Niedźwiedź.